package jjn.carl.greedy;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author Jjn
 * @since 2023/8/1 10:13
 */
public class LeetCode1005 {
    public int largestSumAfterKNegations(int[] nums, int k) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] < 0 && k > 0) {
                k--;
                nums[i] = -nums[i];
            } else {
                break;
            }
        }
        k = k % 2;
        Arrays.sort(nums);
        if (k > 0) {
            nums[0] = -nums[0];
        }
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        return total;
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int total = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[total];
        for (int i = 0; i < total; i++) {
            nums[i] = scanner.nextInt();
        }
        int largestSumAfterKNegations = new LeetCode1005().largestSumAfterKNegations(nums, k);
        System.out.println(largestSumAfterKNegations);
    }
}
